#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution
{
public:
    static vector<int> findAnagrams(string s, string p)
    {
        //优化前：
        // vector<int> ret;
        // unordered_map<char, int> hash1; // hash1每一轮都需要进行更新
        // unordered_map<char, int> hash2;
        // for (int i = 0; i < p.size(); i++)
        // {
        //     // hash2更新
        //     if (hash2.find(p[i]) == hash2.end())
        //         hash2.insert({p[i], 1});
        //     else
        //         hash2[p[i]]++;
        // }
        // for (int left = 0, right = p.size() - 1; right < s.size(); left++, right++)
        // {
        //     // 进窗口：hash1更新
        //     if (!left)
        //     {
        //         for (int i = 0; i <= right; i++)
        //         {
        //             if (hash1.find(s[i]) == hash1.end())
        //                 hash1.insert({s[i], 1});
        //             else
        //                 hash1[s[i]]++;
        //         }
        //     }
        //     else
        //     {
        //         hash1[s[left-1]]--;
        //         if (!hash1[s[left-1]])
        //             hash1.erase(s[left-1]);
        //         if (hash1.find(s[right]) == hash1.end())
        //             hash1.insert({s[right], 1});
        //         else
        //             hash1[s[right]]++;
        //     }
        //     // 判断：hash1.size() == hash2.size() && hash1中各个数是否相等
        //     if (hash1.size() == hash2.size())
        //     {
        //         int flag = 1;         // 最开始假设都有并且数量也相同
        //         for (auto it : hash1) // 遍历hash判断是否都有
        //         {
        //             if (hash2.find(it.first) == hash2.end()) // 没有，则说明种类不一样，break
        //             {
        //                 flag = 0;
        //                 break;
        //             }
        //             else // 有，则判断是否都相等，不相等则break，相等则ret.push_back
        //             {
        //                 if (it.second != hash2[it.first])
        //                 {
        //                     flag = 0;
        //                     break;
        //                 }
        //             }
        //         }
        //         if (flag) // 说明最后都有，且相等
        //         {
        //             ret.push_back(left);
        //         }
        //     }
        // }
        // return ret;
        //优化后：
        vector<int> ret;
        int hash1[26] = { 0 };
        int hash2[26] = { 0 };
        for (int i = 0; i < p.size(); i++)
        {
            // hash2更新
                hash2[p[i] - 'a']++;
        }
        cout << "p.size(): " << p.size() << endl;
        int cnt = 0;//有效字符
        for (int left = 0, right = 0; right < s.size(); right++)
        {
            //进窗口：
            hash1[s[right]-'a']++;
            //进窗口后
            if(hash1[s[right]-'a'] <= hash2[s[right]-'a']) cnt++;//维护有效字符数
            if(right - left + 1 > p.size())//判断
            {
                //出窗口前
                if(hash1[s[left]-'a'] <= hash2[s[left]-'a'])
                    cnt--;//维护有效字符数
                //出窗口
                hash1[s[left++]-'a']--;
            }
            if(cnt == p.size())
                ret.push_back(left);
        }
        return ret;
    }
};

int main()
{
    // string s = "cbaebabacd";
    // string p = "abc";
    string s = "abab";
    string p = "ab";
    auto ans = Solution::findAnagrams(s, p);
    for (auto i : ans)
    {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}